#ifndef GRAPHHANDLER_HPP_INCLUDED
#define GRAPHHANDLER_HPP_INCLUDED



#include <iostream>
#include <set>
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/xml_parser.hpp>
#include <boost/foreach.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/subgraph.hpp>
#include <boost/math/special_functions/beta.hpp>

#include "EditOperationMap.hpp"

//template <typename GeneralGraph> struct vertex_freq_filter;
//template <typename GeneralGraph> struct edge_freq_filter;

/*
    This class loads the data from all the XML-files
    and stores the categories.
*/

using namespace std;
using namespace boost;



struct GSpanStruct;
struct Cluster;

class GraphHandler
{
public:
    static GraphHandler& Instance()
    {
        static GraphHandler singleton;
        return singleton;
    }

    ~GraphHandler();

    // Define the properties of the meta-graph.
    // The meta-graph counts the number of edges between different semantic
    // categories across all files, as well as the occurance of each category (vertex freq).
    struct VertexMetaProperties
    {
        string sName;
        int iFreq;

        VertexMetaProperties() : iFreq(0) {}

        operator std::string () const {
        return sName; }

    };

    struct EdgeMetaProperties
    {
        int iFreq;
        EdgeMetaProperties() : iFreq(0) {}
        EdgeMetaProperties(int _i) : iFreq(_i) {}
        // Could add a vector here pointing to all the graphs which has this connection?
    };


/*
    struct VertexProperties
    {
        string sName;

        template<class Archive>
        void serialize(Archive &ar, const unsigned int version)
        {
            ar & sName;
        }
    };*/

    typedef property<graph_name_t, string> GraphProperties;


    // Store out-edges of each vertex in a std::list. Fast adding.
    // Store vertex set in a std::vector, fast retreival.

    // Definitions of the two graphs.
    // Meta graph has extra properties
    typedef adjacency_list
    <
        listS,       // edge container type
        vecS,//vecS,       // vertex container type
        undirectedS,
        property<vertex_name_t, unsigned int, VertexMetaProperties>,
        EdgeMetaProperties,
        GraphProperties
    > MetaGraph;


    typedef adjacency_list
    <
        setS,//listS,       // edge container type
        vecS,       // vertex container type
        undirectedS,
        //property<vertex_name_t, unsigned int, VertexProperties>,
        property<vertex_name_t, unsigned int>,
        property<edge_index_t, unsigned int>, //no_property,
        property<graph_name_t, string>
    > Graph;

    typedef subgraph<Graph> SubGraph;
    typedef graph_traits<MetaGraph>::vertex_iterator MetaIter_t;
    typedef graph_traits<MetaGraph>::vertex_descriptor MetaVertex;
    typedef graph_traits<MetaGraph>::edge_descriptor MetaEdge;

    typedef graph_traits<Graph>::vertex_iterator Iter_t;
    typedef graph_traits<Graph>::vertex_descriptor Vertex;
    typedef graph_traits<Graph>::edge_descriptor Edge;


    //typedef filtered_graph<MetaGraph, edge_freq_filter<MetaGraph> ,vertex_freq_filter<MetaGraph> > FiltMGraph;

    struct Sorter
    {
        Sorter( const Graph& G ) : m_G(&G) {}
        bool operator() (const Vertex& i,const Vertex& j) const
        {
            return (get(vertex_name, *m_G, i) < get(vertex_name, *m_G, j));
        }


    private:
        const Graph* m_G;
    };

    struct EdgeSorter
    {
    private:
        const Graph* m_G;
    public:
        EdgeSorter( const Graph& G ) : m_G(&G), bTargetNode(true) {}
        bool operator() (const Edge& i,const Edge& j) const
        {
            //target(*first, G)
            if( bTargetNode )
                return (get(vertex_name, *m_G, boost::target(i, *m_G)) < get(vertex_name, *m_G, boost::target(j, *m_G)));
            else
                return (get(vertex_name, *m_G, boost::source(i, *m_G)) < get(vertex_name, *m_G, boost::source(j, *m_G)));
        }

        bool bTargetNode;


    };

    // FUNCTIONS:

    // This function enumerates through all the files
    // located in the specified directory and loads them.
    int LoadAllGraphs(string sDir, int iLimit = -1);

    // Displays all the meta vertices and their count
    void ListMetaVertices() const ;


    // Saves a graph to file (GraphViz format)
    // The user can specify an overlay graph which makes the common vertices/edges red
    void SaveGraph(string sFilename, const Graph& G, const Graph* pOverlay = 0) const;
    void SaveGraph(string sFilename, const Graph& G, vector<const Graph*> pOverlay) const;

    // Saves the meta graph to a file
    void SaveMetaGraph(string sFilename);

    // Removes all those vertices which have no edges from a specific graph
    void RemoveIsolatedVertices(Graph* pG);

    // Removes all those vertices which have no edges on all graphs
    void RemoveIsolatedVertices();

    // This applies a filter to the meta graph, all subsequent calls to functions
    // involving the metagraph will be filtered
    void FilterMetaGraph(int iVertexCutoff, int iEdgeCutoff);

    // This functions filters the graph and erases the original graph (writes it over).
    // This is used for example when combined with merging of concepts.
    // Everything below the cutoff will be excluded.
    // All the vertices with names in the sBlacklist vector will be removed from the graph.
    void FilterTransformMetaGraph(int iVertexCutoff, int iEdgeCutoff);

    // Finds the vertex which has the specified name in any graph g. bMeta specifies
    // if we are searching in the meta graph or not.
    // Returns a pair, first component is a boolean if the vertex was found or not
    // Second component is an iterator pointing to the vector if found.
    /*
    template <typename GeneralGraph>
    pair<bool, typename graph_traits<GeneralGraph>::vertex_iterator>
        FindVertex(string sName, const GeneralGraph& g) const;*/
    pair< bool, Iter_t >
        FindVertex(string sName, const Graph& g) const;

    // Returns a vertex descriptor for the vertex which have iName as
    // internal graph_name property in graph G.
    pair<bool, Vertex> FindVertex(unsigned int iName, const Graph& G) const;

    // This function takes a list of names(ToMerge) and a string with the new name of the
    // resulting merged vertex. I.e, it merges all the vertices to one (maintaining connections).
    void MergeVertices(const set<string>& ToMerge, string sNewName);

    //
    void Blacklist(const set<string>& sBlacklist);

    // Gives the edit distance between G1 and G2
    int EditDistance(const Graph& G1, const Graph& G2) const;

    // Returns true/false depending on if they are equal or not
    bool GraphEqual(const Graph& G1, const Graph& G2) const;

    // Ensures that no graphs are isomorphic to each other
    void RemoveDuplicates(std::vector<Graph>* pVec = 0);

    // Serializes all the graphs and the clustering as well as correlation corefficients to disk
    template<class Archive>
    void serialize(Archive &ar, const unsigned int version);

    // Save/load all the data
    void Save(string sFilename);
    void Load(string sFilename);

    std::vector<Graph>& GetGraphVector() { return m_Graphs; }

    // Returns a graph object of the given ID
    Graph& GetGraph(int iID);

    // Returns the number of graphs
    int GetNumGraphs() const;

    void TransformMetaGraph();

    // Returns the largest common subgraph
    Graph LargestCommonSubGraph(Graph& G1, Graph& G2);

    // Returns true if the smaller of the two graphs is subgraph isomorphic to the larger.
    bool IsSubgraphIsomorph(const Graph& G1, const Graph& G2) const;

    void SaveGSpanData(string sFilename, const vector<Graph>& kVec);

    vector<GSpanStruct> LoadGSpanData(string sFilename);

    vector< vector<Graph*> > StructureClustering(double dTheta, int iMinGraphSize);

    vector<GSpanStruct> GSpan(const vector<Graph>& kVec, double dFreq);

    // Vector of pointers to Graph variant
    vector<GSpanStruct> GSpan(const vector<Graph*>& kVec, double dFreq);

    pair<bool, Graph> GSpanStructure(const vector<Graph*>& kVec, int minSup, int minSize);

    double DeriveProbability(vector<Graph*>& kT, Graph& kInst);

    vector< vector<GraphHandler::Graph> > DecomposeGraphInternal(vector<Graph> Gi,const Graph& G,
               vector< pair<Cluster*, double> > pPatterns);

    Graph GenerateGraphModel(vector<Graph*>& kT);

    vector< Cluster* > StructureClustering2();
    vector< Cluster* > StructureClustering3(double dTheta);

    // Calculates the correlation between each pair of clusters
    void CalculateClusterCorrelations();

    // Returns true if the vertex sets of the graphs are not disjoint
    bool HasVertexCommon(const Graph& G1, const Graph& G2, int iK) const;

    // Returns the position in the m_Graphs vector
    int GetGraphID(const Graph* pG) const;

    // Gives the rank of a vertex, as of now defined simply as the degree
    double VertexRank(Vertex V) const;

    void ClusterComponent(Graph H);

    // Returns the induced subgraph of the vertex set
    Graph InducedSubgraph(vector<Vertex> V, const Graph& G);

    vector<Graph> ConnectedSubgraphs(const Graph& G) const;

    void ConnectedSubgraphs2(const Graph& G);

    vector<GraphHandler::Graph> RareAlgorithm(Graph& G);

    Graph ExampleStepPredict2(const Graph* pPartialGraph = 0);
    Graph ExampleStepPredict2Preprocessed(const Graph* pPartialGraph = 0);
    Graph ExampleStepPredict3(const Graph* pPartialGraph = 0);
    Graph ExampleStepPredict4(const Graph* pPartialGraph = 0);

    Graph GraphUnion( list<Graph>& kGraphs ) const;
    Graph GraphUnion( list<const Graph*>& kGraphs ) const;
    Graph GraphUnion( const vector<Graph>& kGraphs ) const;

    pair< vector< vector< vector<Vertex> > >, bool>
    ConnectedSubgraphInternal(vector<Vertex> vVec,
                              vector<Vertex> vCommon, int iN, vector<int>& kPartition, int iNSeparatorsTotal, int iSep) const;

    int GenerateTestExample(bool bReload = false, int iID = -1, string* sVertexName = 0);
    Graph ExampleStepPredict(const Graph* pPartialGraph = 0);
    void ExampleStepNext();

    vector<Graph> DecomposeGraph(const Graph& G);
    vector<Graph> DecomposeGraph2(const Graph& G);
    vector<Graph> DecomposeGraph3(const Graph& G);

    // Removes those vertices (from all graphs) which has fewer than iThreshold
    // different frequent subgraphs in which it appears
    void BlacklistOnCriterion(int iThreshold);

    pair<GraphHandler::Graph, int> GetOptimalParentOnline(const Graph& GP,
                                                          const vector<Graph>& kVec, int iIndex, const Graph& G, const Graph* pUnion = 0);

    pair<Graph, double> GetOptimalParentOnline2(const Graph& GP,
      const vector<Graph>& kVec, int iIndex, const Graph& G, const Graph* pUnion = 0);

    // Creates a file and saves all those vertices which should be blacklisted according to the threshold
    void SaveBlacklist(string sFilename, int iThreshold);

    // Loads a text file and blacklists each vertex contained in the file (line separated)
    void LoadBlacklist(string sFilename);

    // Iterates through the graph database and removes the graphs which are disconnected
    void RemoveDisconnectedGraphs();

    // Stats functions:
    int GetTotalNumVertices() const;

    int GetTotalNumEdges() const;

    int GetTotalNumLabels() const;

    int GetTotalNumGraphs() const;

    void AssertUniqueLabels();

    int JointGraphSupp(const Graph& G1, const Graph& G2) const;
    double GetGraphCorrelation(const Graph& G1, const Graph& G2) const;

    GraphHandler::Graph BruteForcePredict(const Graph* pPartialGraph = 0);

    void GenerateFrequentEditMaps(const vector<GSpanStruct>& vFreqSubgraphs);

    vector< Graph > kCommon;



    // Probability testing variables:

    vector< pair<Graph, double> > m_kHypothesis;

    vector< Graph > m_kPSubgraphs;

    vector<int> m_iHypSupport;

    int iExcludeGraph;

    // The current complete graph that we're testing against
    Graph* m_pEGraph;

    // The partial graph that we know so far
    Graph m_kPartialG;

    // The prediced graph
    Graph m_kPredictedG;

    // A vector of vertices from m_pEGraph not yet added to the partial graph
    vector<Vertex> m_kNotAdded;

    // A vector of edges from m_pEGraph not yet added to the partial graph
    vector<Edge> m_kNotAddedEdges;


     // Save the correspondence (vertex of m_pEGraph) -> (vertex of partial graph)
    map<Vertex, Vertex> m_PGMap;




// Other non-static member functions
private:
    GraphHandler();                                 // Private constructor
    GraphHandler(const GraphHandler&);                 // Prevent copy-construction
    GraphHandler& operator=(const GraphHandler&);      // Prevent assignment

    // Loads the graph of a single XML-file
    bool LoadSingleGraph(string sFilename);

    pair<string,string> GetNameTypeAttr(const property_tree::ptree::value_type v) const;

    // Enumerate the directory, counting files so we can reserve the vector of graphs
    int CountFilesInDir(string sDir) const;

    // Takes a single graph and merges the vectors
    // in it.
    void MergeVerticesInternal(const set<string>& ToMerge, Graph& G, string sNewName);

    template<typename GeneralGraph>
    void MergeVerticesInternalMeta(const set<string>& ToMerge,
                    GeneralGraph& G, string sNewName);


    // Saves a graph to file (GraphViz format)
    template<typename GeneralGraph>
    void SaveMetaGraphInternal(string sFilename, const GeneralGraph& G) const;


    Graph BlacklistInternal(const Graph& G, const set<string>& sBlacklist);

    // Removes all those graphs G which have |G|=0
    void RemoveEmptyGraphs();

    // Checks if kG is a subgraph of any of kC's parents.
    bool ParentsHasSubgraph(const Cluster& kC, const Graph& kG) const;

    double GetClusterCorrelation(int i, int j) const;

    bool AddCluster(Cluster* pAddTo, const Graph& kMetaG, Cluster* pNewC);

    // Adds a vertex to the partial graph
    void AddExampleVertex(bool bForceAdd = false, string* sVertexName = 0);

    int FindClusterID(const Cluster* pC) const;

    // Adds an edge to the partial graph
    void AddExampleEdge();

    // Gives freq(g1,g2)/|D| where |D| is the number of graphs in the database
    // and freq gives the number of graphs in which both G1 and G2 are contained in
    double JointGraphSupp(const Cluster* G1, const Cluster* G2) const;

    int GetGraphSupportOnline(const Graph& G) const;

    double GetGraphCorrelation(int iG1Supp, int iG2Supp, int iG1G2Supp) const;

    int VertexAdditionsPossible();

    Cluster* GreedyFindBestCluster(const Graph& G, const list<Cluster*>& kTmpV);

    // Finds the parent of pChild which has the largest support
    Cluster* FindOptimalParent(const Cluster* pChild, const list<Cluster*>& kRelevantClusters) const;

    //pair<const Graph*, double> FindOptimalParent(const Graph& pChild) const;
    pair<const Graph*, double> FindOptimalParent(const Graph& pChild,
                                        const vector<Graph>& kVec, int iIndex, const Graph& G) const;


    double GetProbabilityForHypothesis(const Graph& gHyp, const Graph& gPartial);

    bool CheckPartition(const vector<int>& kPart, int iG) const;

    Graph GetDifferenceGraph(const Graph& gHyp, const Graph& gPartial);

    // Generates a set of strings with the names of thoser vertices which has fewer than iThreshold
    // different frequent subgraphs in which it appears
    set<string> InternalGenerateBlacklist(int iThreshold) const;

    // These two functions applies the edit operations specified to the graph GP
    Graph FormResultOfVertexEditOp(const Graph& GP, pair<Vertex, Vertex> vEditOp);
    Graph FormResultOfEdgeEditOp(const Graph& GP, pair<unsigned int, unsigned int> eEditOp);

    //------------------------
    // METIS partitioning functions
    void SaveMetisGraph(string sFilename, const Graph& G);

    vector<Graph> LoadMetisPartition(string sFilename, const Graph& G);

    vector<Graph> MetisPartition(const Graph& G);

    //------------------------

    vector< pair<Cluster*, double> > GetPatterns(const Graph& G);

    //----------------------------
    // Searches pPatterns for any graph that has atleast one vertex in common with G
    pair<bool, Graph*> FindCommonFreqSubgraph(vector< pair<Cluster*, double> >& pPatterns, const Graph& G,
                                              const Graph& kUnion, vector<Graph>& Gi) const;

    //-----------------------------

    pair< bool, list< pair<int, int> > > GetConnectionList(vector<Graph>& graphs);

    // Private members

    // All the semantic types thus far encountered when loading XML-files.
    set<string> m_Types;

    bool m_debug;

    // Each type get a unique number
    map<string, int> m_TypesID;

    // Each type get a unique number
    map<int, string> m_IDTypes;

    int m_iIDCounter;

    bool m_bCorrectPrediction;

    // This takes a type name -> MetaVertex
    map<string, MetaVertex> m_TypeVertexMap;

    MetaGraph m_MetaGraph;

    // This vector stores all the graphs
    vector<Graph> m_Graphs;

    // If the meta graph is filtered
    bool m_bMetaFiltered;

    //vertex_freq_filter<MetaGraph> m_Vertexfilter;
    //edge_freq_filter<MetaGraph> m_Edgefilter;

    // The filtered meta graph
   //FiltMGraph* m_pFiltMGraph;

    vector< Cluster* > clusters;

    // In case we want to enumrate through all the clusters
    // without traversing the tree
    vector< Cluster* > m_pAllclusters;

    vector<EditOperationMap> m_kEditMaps;

    vector<unsigned int> m_iIDVector;

    //typedef pair< Cluster*, Cluster* > CPair;
    typedef pair< int, int > CPair;
    // The correlation coeficcient for each cluster pair
    //map< CPair, double > m_dCorr;
    vector< vector<double> > m_dCorr;

    const Graph* m_RankG;

    set<unsigned int> m_RSet;

    vector< Graph > m_ClusterCores;

    Graph kEditG;

    friend class Vertex_writer;
    friend class AlgorithmStats;

};


struct GSpanStruct
{
    GraphHandler::Graph G;
    int iSupport;
    std::vector<int> kGraphIDs;
};

template<typename RealType>
RealType
binomial(RealType n, RealType k)
{
     return 1.0 / ((n+1) * boost::math::beta(n - k + 1, k + 1));
}

template<class X>
struct sort_pred {

private:
    bool m_bDesc;

public:
    sort_pred(bool bDesc) :m_bDesc(bDesc) {}
    sort_pred() { m_bDesc=false; }

    bool operator()(const std::pair<X,double> &left, const std::pair<X,double> &right) {
        if( !m_bDesc )
            return left.second > right.second;
        else
            return left.second < right.second;
    }
};



    // Template specialized function for the MetaGraph (since it involves further operations).
    //template<>
    //void GraphHandler::MergeVerticesInternal<GraphHandler::MetaGraph>(vector<string> ToMerge, GraphHandler::MetaGraph& G, string sNewName);


#endif // GRAPHHANDLER_HPP_INCLUDED
